import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA
 * Description:  大根堆的实现
 * User: SEKI TOMOKI
 * Date: 2024-09-18
 * Time: 13:28
 */
public class TestHeap {
    public int[] elem;
    public int usedSize;//用于记录堆的节点个数

    /**
     * TeatHeap 的构造方法
     */
    public TestHeap() {
        this.elem = new int[10];
    }

    /**
     * 初始化 elem数组
     * @param array
     */
    public void initElem(int[] array) {
        for(int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    /**
     *根据 elem 数组创建大根堆
     * 创建堆的时候使用向下调整，因为向下调整的时间复杂度 O(N),向上调整的时间复杂度O(N*log(N))
     */
    public void createHeap() {
        //从最后一棵子树开始调整
        int last = usedSize - 1;
        for(int parent = (last-1)/2; parent >=0; parent--) {
            shiftDown(parent, usedSize);
        }
    }

    /**
     * 向下调整
     * @param parent
     * @param usedSize
     */
    private void shiftDown(int parent, int usedSize) {
        //找到孩子节点，默认是左边的节点
        int child = 2*parent + 1;

        //孩子节点的下标不能大于等于数组的长度
        while(child < usedSize) {
            //找到左右孩子节点的最大值
            //要注意右孩子节点也不能越界
            if(child + 1 < usedSize && elem[child] < elem[child + 1]) {
                child = child + 1;
            }

            //和根节点进行比较,如果根节点比孩子节点大就进行交换
            if(elem[child] > elem[parent]) {
                swap(child, parent);
                //交换完成之后，小的元素向下移动，可能导致子树不满足大根堆的性质，
                // 因此需要继续向下调整，进入下一个循环
                parent = child;
                child = 2*parent + 1;
            }else {
                break;//如果根节点已经比孩子节点大了，说明该结构已经满足堆的特性，无需再进入循环向下调整
            }
        }
    }

    /**
     * 堆的插入
     * @param val
     */
    public void offer(int val) {
        //如果数组满了需要先扩容
        if(isFull()) {
            elem = Arrays.copyOf(elem, 2*elem.length);
        }

        //把数据插入到堆的最后一个
        elem[usedSize] = val;
        usedSize++;
        //向上调整
        shiftUp(usedSize - 1);
    }

    private boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 大根堆的向上调整
     */
    public void shiftUp(int child) {
        while(child > 0) {
            int parent = (child - 1) / 2;
            if(elem[child] > elem[parent]) {
                swap(child, parent);
                child = parent;
            }else {
                break;//如果父亲节点已经比孩子节点大，说明已经满足堆的特性，无需再向上调整
            }
        }
    }

    /**
     * 两个元素交换
     * @param index1
     * @param index2
     */
    private void swap(int index1, int index2) {
        int tmp = elem[index2];
        elem[index2] = elem[index1];
        elem[index1] = tmp;
    }

    /**
     * 堆的删除：删除堆顶元素
     */
    public void poll() throws HeapEmptyException{
        if(isEmpty()) {
            throw new HeapEmptyException("这个堆是空的");
        }

        //把 0 下标和最后一个下标的值
        swap(0,usedSize - 1);
        usedSize--;

        //向下调整 0 下标这棵树就行了
        shiftDown(0, usedSize);
    }

    private boolean isEmpty() {
        return usedSize == 0;
    }




    /**
     * top - k 问题，返回最小的前 k 个数据
     * @param arr 数组
     * @param k  表示返回最小的前 k 个数据
     * @return
     */
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            // 实例化匿名内部类 Comparator<Integer> 并重写了 compare 方法。
            // PriorityQueue 默认是小根堆，要实现大根堆，需要提供自定义的比较器。
            // compare 方法返回 o2 - o1，这样保证数值较大的元素具有更高的优先级，形成大根堆。
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        //建立大根堆，堆的大小是 k 。
        // 时间复杂度：O(k*log(k))，有k个节点，每个节点插入需要 log(k)
        for(int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }

        // 从第 k+1 个元素开始比较，如果比堆顶元素小，入堆
        //时间复杂度：O( (N-k)*log(k) )
        for(int i = k; i < arr.length; i++) {
            if(arr[i] < priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        //最后把结果存到一个数组中并返回
        int[] ret = new int[k];
        for(int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }

    /**
     * 从小到大排序：建大根堆
     */
    public void heapSort() {
        if(isEmpty()) {
            throw new HeapEmptyException("这个堆是空的");
        }
        //end 用来指向还未排序的最后一个元素
        int end = usedSize-1;
        while(end > 0) {
            //把最大的元素和最后的元素进行交换
            swap(0, end);
            //此时最大的元素已经有序了，0下标元素向下调整，成为大根堆
            shiftDown(0, end);
            end--;
        }
    }

    /**
     * 打印堆
     * @return
     */
    @Override
    public String toString() {
        StringBuilder ret = new StringBuilder();
        ret.append("[");
        for(int i = 0; i < usedSize; i++) {
            ret.append(elem[i]);
            if(i != usedSize - 1) {
                ret.append(", ");
            }
        }
        ret.append("]");
        return ret.toString();
    }
}
